
// 队列 栈 链表都被称作 线性结构
class Node {
    constructor(element,next) {
        this.element = element; // 存放当前节点的内容
        this.next = next // 下一个指针
    }
    
}
class LinkedList {
    constructor(){
        this.head = null
        this.size = 0; // 当前链表存放数据的个数
    }
    getNode(index){
        let current = this.head; // 根据头部一直向下查找
        for (let i = 0; i < index; i++) {
            current = current.next;
        }
        return current; // 找到所引处返回
    }
    add(index, element) {
        if (arguments.length === 1) {
            element = index;
            index = this.size;
        }
        if (index < 0 || index > this.size) throw new Error('越界');
        if (index === 0) {
            let head = this.head;
            let newHead  = new Node(element, head);
            let last = this.size === 0 ? newHead :this._node(this.size-1);
            this.head = newHead;
            last.next = newHead;
        } else {
            let prevNode = this._node(index - 1);
            prevNode.next = new Node(element, prevNode.next);
        }
        this.size++;
    }
    // 如何实现单向链表的反转？
    // 递归先找到最后一个node，再进行俩俩反转
    reverse(){
        function traversal(head) {
             // 一个节点没有， 或者就一个节点
            if(head == null || head.next == null) return head // 新的头部
            let newHead = traversal(head.next); // 不停的找新头
            // 针对最后一次 newHead 就是4  head 就是3
            head.next.next = head;
            head.next = null;
            return newHead
        }
        return traversal(this.head)
    }
    // 创建一个新的链表
    reverse1(){
        let head = this.head;
        if (head == null || head.next == null) return head;    // 一个节点没有， 或者就一个节点
        let newHead = null;
        while (head) { // 把链表的内容 整个搬运一遍，什么时候没有了就没了
            let temp = head.next; // 先把除了对一个节点的节点保存一下
            head.next = newHead; // 将第一个头 指向新接的节点
            newHead = head; // 让新链表的头指向这个节点
            head = temp; // 将原来的链表更新
        }
        return newHead
    }
    remove(index) {
        if (index < 0 || index >= this.size) throw new Error('越界');
        if (index === 0) {
            if(this.size === 1){ // 删除一个时特殊处理
                    this.head = null;
            }else{
                let last = this._node(this.size-1);
                this.head = this.head.next;
                last.next = this.head;
            }
        }else{
            let prevNode = this._node(index - 1);
            prevNode.next = prevNode.next.next;
        }
        this.size--;
    }
}
module.exports = LinkedList


// 处理头尾 追加 删除性能比较高 （双向链表）
let ll =  new LinkedList()
ll.add('1')
ll.add('2')
ll.add('3')
ll.add('4' )
// ll.remove(2)
ll.add('5' )
ll.add('6' )
// console.dir(ll.reverse1());



